package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/system_class/section11/pojo"
)

/**/
func BinaryTreeMaxWidth(tree *BinaryTree) int {

	var curentEnd *BinaryTree = tree
	var nextEnd *BinaryTree = nil
	//先定义两个指针一个是当前行的最后一个一开始初始化为头节点因为第一行肯定就一个
	//第二个nextEnd是实时变化的一直相当于当前的节点 只有当前行遇到当前行的最后的节点的时候才会变更为curentEnd开启下一行的遍历
	maxWidth := 0
	//记录最大的宽度
	curentWidth := 0
	//记录当前行的宽度
	queue1 := NewQueue1[*BinaryTree]()
	//创建队列
	queue1.Offer(tree)

	for !queue1.IsEmpty() {
		//开始循环
		cur := queue1.Poll()
		if cur.Left != nil {
			queue1.Offer(cur.Left)
			nextEnd = cur.Left
			//实时地等于对应的当前节点的子节点这样子当当前节点为当前行的最后一个节点时，当前行的子节点肯定也是下一行的最后节点
		}
		if cur.Right != nil {
			queue1.Offer(cur.Right)
			nextEnd = cur.Right
		}
		curentWidth++ //遍历当前行时遍历一个后使得宽度++
		if cur == curentEnd {
			if curentWidth > maxWidth { //如果当前宽度大于最大宽度就让当前的值替代最大宽度
				maxWidth = curentWidth
			}
			curentWidth = 0     //重置当前宽度为0
			curentEnd = nextEnd //把当前的最后的子节点也就是下一轮的尾结点赋值给表示当前行最后一个节点开始新一轮的遍历
		}
	}
	return maxWidth
}

func main() {
	node1 := NewBinaryTree(0) // 根节点
	node2 := NewBinaryTree(1)
	node3 := NewBinaryTree(3)
	node4 := NewBinaryTree(4)
	node5 := NewBinaryTree(5)
	node6 := NewBinaryTree(6)
	node7 := NewBinaryTree(7)
	node8 := NewBinaryTree(8)
	node9 := NewBinaryTree(9)
	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5
	node4.Left = node6
	node4.Right = node7
	node5.Left = node8
	node5.Right = node9

	width := BinaryTreeMaxWidth(node1)
	fmt.Println(width)
	PrintTree(node1)
}
